package vip.meeet.algorithm.link;

import java.util.HashMap;
import java.util.Map;


public class Num61 {

    public static void main(String[] args) {

//        ListNode listNode = build("12345");
        ListNode listNode = build("12");
        print(listNode);
        ListNode rs = rotateRight(listNode, 2);
        print(rs);
    }

    public static ListNode rotateRight(ListNode head, int k) {
        if(head == null || k==0 || head.next == null){
            return head;
        }
        int count = 0;
        ListNode tmp = head;
        HashMap<Integer, ListNode> map = new HashMap<>();
        do{
            map.put(count++,tmp);
            tmp = tmp.next;
        }while (tmp != null);


        if(k >= count) {
            k = k % count;
        }

        if(k == 0){
            return head;
        }

        ListNode newhead = map.get(count - k);
        map.get(count - 1).next = map.get(0);
        ListNode last = map.get(count - k - 1);
        if(last != null){
            last.next = null;
        }
        return newhead;
    }

    public static void reverse(Map<Integer,ListNode> map, int start, int end,int k){
        ListNode head = map.get(start);
        head.next = map.get(2 * k -1);
        ListNode pre = null,cur;
        for(int i=start;i<=end;i++){
            cur = map.get(i);
            if(i == start){
                cur.next = map.get(start + 2 * k -1);
            }else {
                cur.next = pre;
            }
            pre = cur;
        }
    }

    public static void swap(ListNode nodeA,ListNode nodeB){
        ListNode tmp;
        if(nodeA.next == nodeB){
            nodeA.next = nodeB.next;
            nodeB.next = nodeA;
        }else {
            tmp = nodeA.next;
            nodeA.next = nodeB.next;
            nodeB.next = tmp;
        }
        tmp = nodeA;
        nodeA = nodeB;
        nodeB = tmp;
    }

    public static ListNode build(String num){
        ListNode first = new ListNode(Integer.parseInt(String.valueOf(num.charAt(0))));
        ListNode tmp = first;
        for(int i=1;i<num.length();i++){
            ListNode cur = new ListNode(Integer.parseInt(String.valueOf(num.charAt(i))));
            tmp.next = cur;
            tmp = cur;
        }
        return first;
    }

    public static void print(ListNode node){
        StringBuilder sb = new StringBuilder();
        do{
            sb.append(node.val).append(" -> ");
            node = node.next;
        }while (node != null);
        System.out.println(sb.subSequence(0,sb.length() - 4));
    }

    public static class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { val = x; }
   }

}
